package com.yanqu.road.server.manager.tomb.astar;


import java.math.BigInteger;
import java.util.*;

public class AStar {

    public static void main(String[] args) {
        int[][] grip = {
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        };

        Coordinate start = Coordinate.newInstance(1, 1);
        Coordinate end = Coordinate.newInstance(8, 18);
        AStar aStar = new AStar(grip, 10, 20, start, end);
        aStar.star();

    }


    private Coordinate start;
    private Coordinate end;

    private int[][] grip;

    private Map<String, Node> m_openMap = new HashMap<>();
    private Map<String, Node> m_closeMap = new HashMap<>();

    private Node m_endNode;

    private int maxX;
    private int maxY;

    public AStar(int[][] grip, int maxX, int maxY, Coordinate start, Coordinate end) {
        this.grip = grip;
        this.maxX = maxX - 1;
        this.maxY = maxY - 1;

        this.start = start;
        this.end = end;

        Node node = new Node(start, null, 0, 0);
        this.m_openMap.put(node.getCoordinate().getKey(), node);
    }

    public List<Coordinate> star() {
        int whileTimes = 0;
        while (this.m_openMap.size() > 0 && this.m_endNode == null) {
            if (whileTimes >= 100000) {
                break;
            }
            whileTimes++;
            ArrayList<Node> nodes = new ArrayList<>(m_openMap.values());
            nodes.sort(Comparator.comparing(Node::getM_f));
            Node node = nodes.get(0);
            m_openMap.remove(node.getCoordinate().getKey());
            this.operateNeighborNode(node);
            this.m_closeMap.put(node.getCoordinate().getKey(), node);
        }
        if (this.m_endNode == null) {
            return null;
        }
        List<Coordinate> list = new ArrayList<>();
        int whileTimes1 = 0;
        Node node = this.m_endNode;
        while (node != null) {
            if (whileTimes1 >= 10000) {
                break;
            }
            whileTimes1++;
            list.add(node.getCoordinate());
            node = node.getParent();
        }
        return list;
    }


    public void operateNeighborNode(Node node) {
        for (int i = -1; i < 2; i++) {
            for (int j = -1; j < 2; j++) {
                if (Math.abs(i) == Math.abs(j)) {
                    continue;
                }
                int x = node.getCoordinate().getX() + i;
                int y = node.getCoordinate().getY() + j;
                Coordinate coordinate = Coordinate.newInstance(x, y);
                if (m_closeMap.containsKey(coordinate.getKey())) {
                    continue;
                }
                if (x == -1 || y == -1) {
                    continue;
                }
                int p = this.grip[x][y];
                if (p == 1) {
                    if (!coordinate.equals(this.end)) {
                        continue;
                    }

                }
                this.addNeighborNodeInQueue(node, coordinate);
            }
        }

    }

    public void addNeighborNodeInQueue(Node parentNode, Coordinate coordinate) {
        int node_g = parentNode.getM_g() + 1;
        if (this.m_openMap.containsKey(coordinate.getKey())) {
            if (node_g < this.m_openMap.get(coordinate.getKey()).getM_g()) {
                this.m_openMap.get(coordinate.getKey()).setM_g(node_g);
                this.m_openMap.get(coordinate.getKey()).setParent(parentNode);
            }
        } else {
            Node node = new Node(coordinate, parentNode, node_g, getToEndDistance(coordinate, this.end));
            if (coordinate.equals(this.end)) {
                this.m_endNode = node;
            } else {
                this.m_openMap.put(node.getCoordinate().getKey(), node);
            }
        }
    }


    public static int getToEndDistance(Coordinate coordinate, Coordinate coordinate1) {
        int x = Math.abs(coordinate1.getX() - coordinate.getX());
        int y = Math.abs(coordinate1.getY() - coordinate.getY());
        return x + y;
    }

}
